package sortieren;

public class HeapSort extends GetSwapSorter{
  public HeapSort(){ super(0); }

  @Override
  protected void sort(){
    int anz=length();
    for(int end=1; end<anz; end++) upheap(end);
    for(int end=anz-1; end>0; end--){
      swap(0, end);
      downheap(end);
    }
  }
  
  private void upheap(int pos){
    int up, wander=get(pos);
    while((up=father(pos))>=0 && wander>get(up)){
      swap(up, pos);
      pos=up;
    }
  }
  
  private void downheap(int over){
    int down=0, pos=0, wander=get(pos);
    while(down<(down=bigson(pos, over)) && wander<bigson){
      swap(pos, down);
      pos=down;
    }
  }
  
  private int father(int i){return (i+1)/2-1;}

  private int bigson;
  private int bigson(int i, int over){
    int rechts=(i+1)*2;
    int links=rechts-1;
    if(links>=over) return i;
    int rson, lson=get(links);
    if(rechts>=over){
      rechts=links;
      rson=lson;
    } else rson=get(rechts);
    if(rson>lson){
      bigson=rson;
      return rechts;
    } else{
      bigson=lson;
      return links;
    }
  }
}
